<?php

set_time_limit(0);
class TSPSolver {
	private $data;
	private $visited;
	private $unvisited;
	private $fileName;
	private $pathLength;
	private $globalDistances;
	private $swapped;
	private $optimisation;
	
	public function __construct($optimisation = false) {
		$this->data 			= array();
		$this->visited 			= array();
		$this->unvisited 		= array();
		$this->pathLength		= 0;
		$this->globalDistances 	= array();
		$this->swapped			= array();
		$this->optimisation		= $optimisation;
	}
	
	public function read($fileName) {
		$this->fileName = $fileName;
		$file = fopen($fileName . '.txt', 'r');
		$header = fgets($file);
		
		$count = 1;
		while (!feof($file)) {
			$line = fgets($file);			
			$row = preg_split('/\s+/', $line);
			
			if (count($row) < 2) {
				break;
			}
			
			$this->data[$count] = array($row[0], $row[1]);
			$this->globalDistances[$count] = array();
			$this->swapped[$count] = array();
			$count++;
		}
		
		fclose($file);
	}
	
	public function findOptimal() {
		$best = 999999999999;
		$bestStartNode = 1;
		foreach ($this->data as $node => $coords) {
			$this->reset();
			$solution = $this->nearestNeighbor($node);
			if ($this->pathLength < $best) {
				$best = $this->pathLength;
				$bestStartNode = $node;
			}
			
		}
		$this->reset();
		echo $best . ' ' . $bestStartNode;
	}
	
	public function reset() {
		$this->pathLength = 0;
		$this->visited = array();
	}
	
	private function resetGlobal() {
		foreach ($this->swapped as $i => $arr) {
			$this->swapped[$i] = array();
			$this->globalDistances[$i] = array();
		}
	}
	
	public function HillClimbing() {
		$trials = 1;
		
		while ($trials <= 10) {
			$maxIterations = 10;
			$current = rand(1, count($this->data));
			$best = $current;
			$currentSolution = $this->nearestNeighbor($current);
			$bestSolution = $currentSolution;
			$currentBest = $this->getSolutionPathLength($currentSolution);
			$bestCost = $currentBest;
			
			while ($maxIterations > 0) {
				while (true) {
					$candidate = $this->getRandomNeighbor($current);
					$candidateSolution = $this->swapNodes($currentSolution, $current, $candidate);
					
					$cost = $this->getSolutionPathLength($candidateSolution);
					if ($cost < $bestCost) {
						$currentBest = $cost;
						$currentSolution = $candidateSolution;
						$current = $candidate;
						$this->resetGlobal();
						break;
					}
					if (count($this->swapped) == count($this->data)) {
						$this->resetGlobal();
						break;
					}
				}
					
					
				if ($currentBest < $bestCost) {
					$bestCost = $currentBest;
					$bestSolution = $currentSolution;
					$best = $current;
				}
					
				$current = rand(1, count($this->data));
				$currentSolution = $this->nearestNeighbor($current);
				$currentBest = $this->getSolutionPathLength($currentSolution);
				
					
				$maxIterations--;
			}
			
			
			/* Used in swog file creation */
			$this->pathLength = $this->getSolutionPathLength($currentSolution);
			$this->visited = $currentSolution;
			//$this->createSwogFile('TSP_1000_' . $trials);
			
			$this->reset();
			
			$trials++;
		}
		
		return $currentSolution;
	}
	
	
	private function swapNodes($solution, $current, $candidate) {
		$temp = $solution[$current];
		$solution[$current] = $solution[$candidate];
		$solution[$candidate] = $temp;
		
		return $solution;
	}
	
	private function swapRandomNodes($solution) {
		$n = count($solution);
		$a = rand(1, $n);
		$b = rand(1, $n);
		while (abs($a - $b) <= 1) {
			$a = rand(1, $n);
			$b = rand(1, $n);
		}
		
		$temp = $solution[$a];
		$solution[$a] = $solution[$b];
		$solution[$b] = $temp;
		
		return $solution;
	}
	
	public function getRandomNeighbor($current) {
		$neighbor = rand(1, count($this->data));
		$count = 0;
		while ($current == $neighbor || isset($this->swapped[$current][$neighbor])) {
// 			var_dump(isset($this->swapped[$current][$neighbor]));
// 			echo $current . ' ' . $neighbor . '<br>';
// 			if ($count == 100) {
// 				die('x');
// 			}
			$neighbor = rand(1, count($this->data));
// 			$count++;
		}

		$this->swapped[$neighbor][$current] = true;
		$this->swapped[$current][$neighbor] = true;
		
		return $neighbor;
	}
	
	public function getSolutionPathLength($solution) {		
		$pathLength = 0;
		$first = current(array_keys($solution));
		$from = $first;
		foreach ($solution as $to) {
			if ($first == $to) {
				continue;
			}
			
			if ($this->optimisation && isset($this->globalDistances[$from][$to])) {
				$distance = $this->globalDistances[$from][$to];
			} else {
				$distance = $this->d($this->data[$from], $this->data[$to]);
				$this->globalDistances[$from][$to] = $distance; /* Symmetric */
				$this->globalDistances[$to][$from] = $distance;
			}

			$from = $to;
			
			$pathLength += $distance;
		}

		if ($this->optimisation && isset($this->globalDistances[$from][$first])) {
			$distance = $this->globalDistances[$from][$first];
		} else {
			$distance = $this->d($this->data[$from], $this->data[$first]);
			$this->globalDistances[$from][$first] = $distance; /* Symmetric */
			$this->globalDistances[$first][$from] = $distance;
		}

		$pathLength += $distance;
		
		return $pathLength;
	}
	
	public function nearestNeighbor($node = 1, $solution = null) {
		$this->unvisited = $this->data;

		$start = $node;
		while (count($this->unvisited) > 0) {
			$this->visited[$node] = $node;
			$distances = $this->getDistances($node);
			$destination = current(array_keys($distances));
			$weight = array_shift($distances);
			unset($this->unvisited[$node]);
			if ($destination != 0) {
				$node = $destination;
			}
			
			$this->pathLength += $weight;

		}
		
		$this->pathLength += $this->d($this->data[$node], $this->data[$start]);
		
		return $this->visited;
	}
	
	public function getDistances($source) {
		$sourceCoords = $this->unvisited[$source];
		$distances = array();
		foreach ($this->unvisited as $node => $coords) {
			if ($node != $source) {
				$distances[$node] = $this->d($sourceCoords, $coords);
			}
		}
		
		asort($distances);
		
		return $distances;
	}
	
	/* Euclidean Distance */
	private function d($a, $b) {
		list($x1, $y1) = $a;
		list($x2, $y2) = $b;
		
		return sqrt(pow($x1 - $x2, 2) + pow($y1 - $y2, 2));
	}
	
	public function createSwogFile($fileName = null) {
		
		if ($fileName == null) {
			$fileName = $this->fileName;
		}
		$file = fopen($fileName . '.swog', 'w+');
		
		$description = array(
			'new 1100,1100',
			'string 20,20 {Taivo Teder, Hill-Climbing, Score: ' . $this->pathLength . '} :tekst',
			'coordsys west south right up',
			'origin 50,50'
		);
		foreach ($description as $line) {
			fwrite($file, $line . PHP_EOL);
		}
		
		foreach ($this->data as $i => $coords) {
			fwrite($file, 'fcircle ' . implode(',', $coords) . ' 3 :p' . $i . PHP_EOL);
		}
		
		
		
		$from = array_shift($this->visited);
		$first = $from;
		
		foreach ($this->visited as $to) {
			fwrite($file, 'line (p' . $from . ') (p' . $to .')' . PHP_EOL);
			$from = $to;
		}
		
		fwrite($file, 'line (p' . $from . ') (p' . $first .')' . PHP_EOL);
		
		fclose($file);
	}
}


$fileName = 'TSP_100';
$tspSolver = new TSPSolver(true);
$tspSolver->read($fileName);

// /**
// //  * array (size=10)
//   4 =>  4
//   8 =>  8
//   5 =>  5
//   6 =>  6
//   3 =>  3
//   7 =>  7
//   2 =>  2
//   10 =>  10
//   1 =>  1
//   9 =>  9
//  */

var_dump($tspSolver->getSolutionPathLength(array(
1 =>  1,
84 =>  84,
16 =>  16,
26 =>  26,
70 =>  70,
47 =>  47,
61 =>  61,
6 =>  6,
2 =>  2,
40 =>  40,
31 =>  31,
23 =>  23,
59 =>  59,
30 =>  30,
14 =>  14,
67 =>  67,
87 =>  87,
57 =>  57,
90 =>  90,
7 =>  7,
64 =>  64,
69 =>  69,
54 =>  54,
13 =>  13,
48 =>  48,
89 =>  89,
36 =>  36,
63 =>  63,
62 =>  62,
96 =>  96,
83 =>  83,
92 =>  92,
35 =>  35,
24 =>  24,
22 =>  22,
42 =>  42,
95 =>  95,
8 =>  8,
45 =>  45,
56 =>  56,
51 =>  51,
15 =>  15,
41 =>  41,
66 =>  66,
18 =>  18,
25 =>  25,
17 =>  17,
80 =>  80,
76 =>  76,
85 =>  85,
50 =>  50,
44 =>  44,
20 =>  20,
5 =>  5,
34 =>  34,
37 =>  37,
68 =>  68,
52 =>  52,
86 =>  86,
81 =>  81,
3 =>  3,
77 =>  77,
99 =>  99,
88 =>  88,
98 =>  98,
10 =>  10,
94 =>  94,
75 =>  75,
38 =>  38,
78 =>  78,
65 =>  65,
12 =>  12,
79 =>  79,
71 =>  71,
82 =>  82,
33 =>  33,
39 =>  39,
27 =>  27,
100 =>  100,
55 =>  55,
28 =>  28,
4 =>  4,
21 =>  21,
9 =>  9,
11 =>  11,
29 =>  29,
97 =>  97,
58 =>  58,
46 =>  46,
93 =>  93,
49 =>  49,
73 =>  73,
32 =>  32,
74 =>  74,
53 =>  53,
72 =>  72,
43 =>  43,
91 =>  91,
60 =>  60,
19 =>  19,
)));
//$tspSolver->HillClimbing();
//$tspSolver->findOptimal();

// $solution = $tspSolver->nearestNeighbor(2);
// // var_dump($solution);
// echo '<br>';
// echo $tspSolver->getSolutionPathLength($solution);